{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Closest Binary Search Tree Value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二分查找 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: closestValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最接近的二叉搜索树值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给你二叉搜索树的根节点 <code>root</code> 和一个目标值 <code>target</code> ，请在该二叉搜索树中找到最接近目标值 <code>target</code> 的数值。如果有多个答案，返回最小的那个。\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/12/closest1-1-tree.jpg\" style=\"width: 292px; height: 302px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [4,2,5,1,3], target = 3.714286\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1], target = 4.428571\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目在范围 <code>[1, 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= target &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [closest-binary-search-tree-value](https://leetcode.cn/problems/closest-binary-search-tree-value/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [closest-binary-search-tree-value](https://leetcode.cn/problems/closest-binary-search-tree-value/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,5,1,3]\\n3.714286', '[1]\\n4.428571']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def closest_value(self, cur: TreeNode, target: float) -> (Optional[int], float):\n",
    "        if cur is None:\n",
    "            return (None, float(\"inf\"))\n",
    "        \n",
    "        cands: List[int] = [0] * 3\n",
    "        diffs: List[float] = [0] * 3\n",
    "        cands[0], diffs[0] = self.closest_value(cur.left, target)\n",
    "        cands[1], diffs[1] = self.closest_value(cur.right, target)\n",
    "        cands[2], diffs[2] = cur.val, abs(cur.val - target)\n",
    "        \n",
    "        closest, min_diff = 0, float(\"inf\")\n",
    "        for i in range(len(cands)):\n",
    "            if diffs[i] < min_diff:\n",
    "                closest = cands[i]\n",
    "                min_diff = diffs[i]\n",
    "\n",
    "        return (closest, min_diff)\n",
    "\n",
    "    def closestValue(self, root: TreeNode, target: float) -> int:\n",
    "        return self.closest_value(root, target)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        gap = float(\"inf\")\n",
    "        closest = float(\"inf\")\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return\n",
    "\n",
    "            nonlocal gap, closest\n",
    "\n",
    "            if gap > abs(target - node.val):\n",
    "                gap = abs(target - node.val)\n",
    "                closest = node.val\n",
    "            elif gap == abs(target - node.val):\n",
    "                closest = min(closest, node.val)\n",
    "\n",
    "\n",
    "            if node.val <= target:\n",
    "                dfs(node.right)\n",
    "            else:\n",
    "                dfs(node.left)\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        return closest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.target_val = None\n",
    "        self.gap = float('inf')\n",
    "\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        if not root: return\n",
    "        self.closestValue(root.left, target)\n",
    "        if abs(root.val-target) < self.gap:\n",
    "            self.gap = abs(root.val-target)\n",
    "            self.target_val = root.val\n",
    "        self.closestValue(root.right, target)\n",
    "\n",
    "        return self.target_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        # https://www.youtube.com/watch?v=wued6gzSjI4&ab_channel=RenZhang\n",
    "        #注意改了test case所以有些区别，比如target =3.5， 应该返回3 而不是4\n",
    "        #如果两者距离目标的差的绝对值相同，我们会选择较小的那个值。）\n",
    "# 面试时解释思路：\n",
    "\n",
    "# 问题的核心:\n",
    "# 首先，我们要找到BST中最接近给定目标值的节点。BST的一个关键属性是，对于任何节点，其左子树的所有节点的值都小于该节点，\n",
    "# 而右子树的所有节点的值都大于该节点。\n",
    "\n",
    "# 简单直观的方法:\n",
    "# 一个直接的方法是遍历整个树，记录最接近目标值的节点。但是，由于BST的特性，我们实际上不需要遍历所有节点。\n",
    "\n",
    "# 优化的方法:\n",
    "\n",
    "# 我们从根节点开始，初始化 candidate 为根节点的值。(复制一个根节点的值)， while root\n",
    "# 在每一步，我们比较当前节点的值与目标值：\n",
    "# 如果它们相等，那么我们已经找到了最接近的值，可以直接返回。\n",
    "# 如果当前节点的值小于目标值，那么我们知道应该继续在右子树中查找，因为右子树中的所有值都比当前节点大。\n",
    "# 如果当前节点的值大于目标值，我们则在左子树中查找。\n",
    "# 更新最接近的值:\n",
    "# 在每一步，我们都会检查当前节点的值是否比我们到目前为止找到的最接近的值更接近目标值。如果是，我们更新 res。\n",
    "\n",
    "# 结束条件:\n",
    "# 我们继续这个过程，直到我们到达叶子节点或找到与目标值完全匹配的节点。\n",
    "\n",
    "#O (H)\n",
    "# O(1)\n",
    "\n",
    "# 返回结果:\n",
    "# 最后，我们返回 res，它存储了最接近目标值的节点的值。\n",
    "        \n",
    "        candidate = root.val #初始化为root。val 根节点？？\n",
    "\n",
    "        while root:\n",
    "\n",
    "            if root.val == target:\n",
    "                return root.val\n",
    "\n",
    "            if  abs(root.val -target) < abs(candidate-target) or \\\n",
    "                   ( abs(root.val -target) == abs(candidate-target) and root.val<candidate):\n",
    "                   candidate = root.val\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "            if root.val< target:\n",
    "                root = root.right\n",
    "            else:\n",
    "                root = root.left\n",
    "        return candidate\n",
    "#         node = root\n",
    "#         res = root.val\n",
    "\n",
    "#         while node: #still  a valid node \n",
    "# #             我们使用两个条件来检查是否应该更新 res:\n",
    "# # 当前节点的值是否比 res 更接近目标。\n",
    "# # 如果两者距离目标的差的绝对值相同，我们会选择较小的那个值。\n",
    "#             # 如果当前节点更接近目标，或者距离相同但值较小，更新结果\n",
    "#             if abs(target - node.val) < abs(target - res) or \\\n",
    "#              (abs(target - node.val) == abs(target - res) and node.val < res):\n",
    "#                 res = node.val\n",
    "\n",
    "#             # 根据当前节点的值移动到左子树或右子树\n",
    "#             if node.val < target:\n",
    "#                 node = node.right\n",
    "#             else:\n",
    "#                 node = node.left\n",
    "\n",
    "#         return res\n",
    "\n",
    "        # node = root\n",
    "\n",
    "        # res = node.val\n",
    "        # while node:\n",
    "        #     if node.val == target:\n",
    "        #         return node.val\n",
    "        #     if abs(node.val -target)  < abs(res-target) or \\\n",
    "        #      (abs(node.val -target)  == abs(res-target) and node.val < res) :\n",
    "        #         res = node.val\n",
    "            \n",
    "        #     if node.val > target:\n",
    "        #         node = node.left #到最下面node，node.left=None， 然后下一轮while就停了\n",
    "        #     else: #必须用else，如果再来个if，可能上面刚更新了下面就又更新了，不对，一次性只能更新一次\n",
    "        #         node = node.right\n",
    "        # return res\n",
    "            \n",
    "            \n",
    "\n",
    "    \n",
    "# 目标值: target = 3.5\n",
    "\n",
    "# 初始化:\n",
    "# node = 4\n",
    "# res = 4\n",
    "# 进入第一次循环:\n",
    "# 当前 node.val = 4\n",
    "# 计算差值 abs(target - node.val) = abs(3.5 - 4) = 0.5\n",
    "# 当前 res 的差值: abs(3.5 - 4) = 0.5\n",
    "# 由于 node.val 和 res 的差值相同，并且 node.val 不小于 res，所以不更新 res。\n",
    "# 因为 node.val 大于 target，我们要去 node 的左子节点。\n",
    "# 更新 node = node.left = 2\n",
    "\n",
    "# 进入第二次循环:\n",
    "# 当前 node.val = 2\n",
    "# 计算差值 abs(target - node.val) = abs(3.5 - 2) = 1.5\n",
    "# 当前 res 的差值仍然是 0.5。\n",
    "# 由于 node.val 的差值大于 res 的差值，所以不更新 res。\n",
    "# 因为 node.val 小于 target，我们要去 node 的右子节点。\n",
    "# 更新 node = node.right = 3\n",
    "\n",
    "# 进入第三次循环:\n",
    "# 当前 node.val = 3\n",
    "# 计算差值 abs(target - node.val) = 0.5\n",
    "# 当前 res 的差值还是 0.5。\n",
    "# 但由于 node.val 的差值与 res 的差值相同，并且 node.val 小于 res，所以更新 res = 3。\n",
    "# 因为 node.val 小于 target，但是 node 没有右子节点，所以更新 node = None。\n",
    "# 循环结束:\n",
    "# node 是 None，所以循环结束。\n",
    "# 返回的结果是 res = 3。\n",
    "\n",
    "\n",
    "        # node = root\n",
    "        # candidate = node.val\n",
    "\n",
    "        # while node:\n",
    "\n",
    "        #     if node.val == target:\n",
    "        #         return node.val\n",
    "            \n",
    "        #     if abs(node.val-target) < abs(candidate-target) or (abs(node.val-target) == abs(candidate-target) and node.val<candidate):\n",
    "        #         candidate = node.val\n",
    "\n",
    "\n",
    "        #     if node.val < target:\n",
    "        #         node = node.right\n",
    "        #     else:\n",
    "        #         node = node.left\n",
    "\n",
    "        # return candidate\n",
    "# 对于输入 root = [4,2,5,1,3] 和 target = 3.714286 的模拟：\n",
    "\n",
    "# 初始化:\n",
    "\n",
    "# node = 4\n",
    "# res = 4\n",
    "# 进入 while 循环:\n",
    "\n",
    "# node.val (4) 不等于 target，所以跳过第一个 if 语句。\n",
    "# 计算差值:\n",
    "# ∣\n",
    "# 4\n",
    "# −\n",
    "# 3.714286\n",
    "# ∣\n",
    "# =\n",
    "# 0.285714\n",
    "# ∣4−3.714286∣=0.285714\n",
    "# 当前 res = 4，其差值为 0.285714。\n",
    "# 因为两者的差值相同但 node.val 并不小于 res，所以不会更新 res。\n",
    "# 由于 node.val = 4 大于 target，所以移动到左子节点 2。\n",
    "# 继续 while 循环:\n",
    "\n",
    "# node.val (2) 不等于 target。\n",
    "# 计算差值:\n",
    "# ∣\n",
    "# 2\n",
    "# −\n",
    "# 3.714286\n",
    "# ∣\n",
    "# =\n",
    "# 1.714286\n",
    "# ∣2−3.714286∣=1.714286\n",
    "# res 与 target 的差值 (0.285714) 更小，所以不会更新 res。\n",
    "# 由于 node.val = 2 小于 target，所以移动到右子节点 3。\n",
    "# 继续 while 循环:\n",
    "\n",
    "# node.val (3) 不等于 target。\n",
    "# 计算差值:\n",
    "# ∣\n",
    "# 3\n",
    "# −\n",
    "# 3.714286\n",
    "# ∣\n",
    "# =\n",
    "# 0.714286\n",
    "# ∣3−3.714286∣=0.714286\n",
    "# res 与 target 的差值 (0.285714) 更小，所以不会更新 res。\n",
    "# 由于 node.val = 3 小于 target，所以移动到右子节点，但 3 节点的右子节点是 None。\n",
    "# node 为 None，结束 while 循环。\n",
    "\n",
    "# 返回 res，其值为 4，与预期的输出一致。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "\n",
    "        L, U = float('-inf'), float('inf')\n",
    "        def dfs(node):\n",
    "            nonlocal L, U\n",
    "            if node.val > target:\n",
    "                U = min(U,node.val)\n",
    "                if node.left:\n",
    "                    dfs(node.left)\n",
    "            if node.val <= target:\n",
    "                L = max(L,node.val)\n",
    "                if node.right:\n",
    "                    dfs(node.right)\n",
    "        dfs(root)\n",
    "        if target - L <= U - target:\n",
    "            return L\n",
    "        else:\n",
    "            return U\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        \n",
    "        def dfs_close(root: TreeNode ):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return \n",
    "            if abs(root.val - target )<abs(ans - target):\n",
    "            \n",
    "                ans = root.val\n",
    "            elif abs(root.val - target ) == abs(ans - target):\n",
    "                ans =min(root.val,ans)\n",
    "            if root.val >target:\n",
    "                \n",
    "                dfs_close(root.left)\n",
    "            elif root.val < target:\n",
    "                dfs_close(root.right)\n",
    "            return \n",
    "        ans = inf\n",
    "        dfs_close(root)\n",
    "        #print(ans,type(ans))\n",
    "        return ans\n",
    "\n",
    "    '''# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            if abs(node.val - target) < abs(ans - target):\n",
    "                ans = node.val\n",
    "            if node.val > target:\n",
    "                dfs(node.left)\n",
    "            elif node.val < target:\n",
    "                dfs(node.right)\n",
    "            return\n",
    "\n",
    "        ans = root.val\n",
    "        dfs(root)\n",
    "        return ans'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        self.res=float(\"inf\") #取float正无穷\n",
    "        def findclose(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if abs(root.val-target)<abs(target-self.res):\n",
    "                self.res=root.val\n",
    "            elif abs(root.val-target) == abs(target-self.res):\n",
    "                self.res = min(root.val, self.res)\n",
    "            \n",
    "            if target>root.val:\n",
    "                findclose(root.right)\n",
    "            else:\n",
    "                findclose(root.left)\n",
    "        findclose(root)\n",
    "        return self.res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\r\n",
    "        node = root\r\n",
    "        res = root.val\r\n",
    "        has_change = True\r\n",
    "        while has_change:\r\n",
    "            has_change = False\r\n",
    "            res = min(res, node.val,key=lambda x:(abs(x - target), x))\r\n",
    "            if node.left is not None and target < node.val:\r\n",
    "                node = node.left\r\n",
    "                has_change = True\r\n",
    "            elif node.right is not None and target > node.val:\r\n",
    "                node = node.right\r\n",
    "                has_change = True\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        node = root\n",
    "        res = root.val\n",
    "        has_change = True\n",
    "        while has_change:\n",
    "            has_change = False\n",
    "            res = min(res, node.val,key=lambda x:(abs(x - target), x))\n",
    "            if node.left is not None and target < node.val:\n",
    "                node = node.left\n",
    "                has_change = True\n",
    "            elif node.right is not None and target > node.val:\n",
    "                node = node.right\n",
    "                has_change = True\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        if not root:\n",
    "            return \n",
    "        self.smaller = float('-inf')\n",
    "        self.larger = float('inf')\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return                \n",
    "            if root.val == target:\n",
    "                self.smaller = root.val\n",
    "                self.larger = root.val\n",
    "                return root.val\n",
    "            elif root.val < target:\n",
    "                self.smaller = max(self.smaller, root.val)\n",
    "                helper(root.right)\n",
    "            else:\n",
    "                self.larger = min(self.larger, root.val)\n",
    "                helper(root.left)\n",
    "        \n",
    "        helper(root)\n",
    "        if target - self.smaller <= self.larger - target:\n",
    "            return self.smaller\n",
    "        else:\n",
    "            return self.larger\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        global res, diff, f\n",
    "\n",
    "        f = 0\n",
    "        res = root.val\n",
    "        diff = float('inf')\n",
    "\n",
    "        self.traverse_bst(root, target)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "    def traverse_bst(self, root, target):\n",
    "        global res, diff, f\n",
    "\n",
    "        if root:\n",
    "            ans = abs(root.val - target)\n",
    "            if ans <= diff:\n",
    "                if ans == diff:\n",
    "                    f = 1\n",
    "                \n",
    "\n",
    "                if f and ans == diff:\n",
    "                    res = min(res, root.val)\n",
    "                else:\n",
    "                    res = root.val\n",
    "\n",
    "                diff = abs(root.val - target)\n",
    "\n",
    "            self.traverse_bst(root.left, target)\n",
    "            self.traverse_bst(root.right, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        # https://www.youtube.com/watch?v=wued6gzSjI4&ab_channel=RenZhang\n",
    "        #注意改了test case所以有些区别，比如target =3.5， 应该返回3 而不是4\n",
    "        #如果两者距离目标的差的绝对值相同，我们会选择较小的那个值。）\n",
    "# 面试时解释思路：\n",
    "\n",
    "# 问题的核心:\n",
    "# 首先，我们要找到BST中最接近给定目标值的节点。BST的一个关键属性是，对于任何节点，其左子树的所有节点的值都小于该节点，\n",
    "# 而右子树的所有节点的值都大于该节点。\n",
    "\n",
    "# 简单直观的方法:\n",
    "# 一个直接的方法是遍历整个树，记录最接近目标值的节点。但是，由于BST的特性，我们实际上不需要遍历所有节点。\n",
    "\n",
    "# 优化的方法:\n",
    "\n",
    "# 我们从根节点开始，初始化 res 为根节点的值。\n",
    "# 在每一步，我们比较当前节点的值与目标值：\n",
    "# 如果它们相等，那么我们已经找到了最接近的值，可以直接返回。\n",
    "# 如果当前节点的值小于目标值，那么我们知道应该继续在右子树中查找，因为右子树中的所有值都比当前节点大。\n",
    "# 如果当前节点的值大于目标值，我们则在左子树中查找。\n",
    "# 更新最接近的值:\n",
    "# 在每一步，我们都会检查当前节点的值是否比我们到目前为止找到的最接近的值更接近目标值。如果是，我们更新 res。\n",
    "\n",
    "# 结束条件:\n",
    "# 我们继续这个过程，直到我们到达叶子节点或找到与目标值完全匹配的节点。\n",
    "\n",
    "# 返回结果:\n",
    "# 最后，我们返回 res，它存储了最接近目标值的节点的值。\n",
    "        \n",
    "\n",
    "#         node = root\n",
    "#         res = root.val\n",
    "\n",
    "#         while node: #still  a valid node \n",
    "# #             我们使用两个条件来检查是否应该更新 res:\n",
    "# # 当前节点的值是否比 res 更接近目标。\n",
    "# # 如果两者距离目标的差的绝对值相同，我们会选择较小的那个值。\n",
    "#             # 如果当前节点更接近目标，或者距离相同但值较小，更新结果\n",
    "#             if abs(target - node.val) < abs(target - res) or \\\n",
    "#              (abs(target - node.val) == abs(target - res) and node.val < res):\n",
    "#                 res = node.val\n",
    "\n",
    "#             # 根据当前节点的值移动到左子树或右子树\n",
    "#             if node.val < target:\n",
    "#                 node = node.right\n",
    "#             else:\n",
    "#                 node = node.left\n",
    "\n",
    "#         return res\n",
    "\n",
    "        # node = root\n",
    "\n",
    "        # res = node.val\n",
    "        # while node:\n",
    "        #     if node.val == target:\n",
    "        #         return node.val\n",
    "        #     if abs(node.val -target)  < abs(res-target) or \\\n",
    "        #      (abs(node.val -target)  == abs(res-target) and node.val < res) :\n",
    "        #         res = node.val\n",
    "            \n",
    "        #     if node.val > target:\n",
    "        #         node = node.left #到最下面node，node.left=None， 然后下一轮while就停了\n",
    "        #     else: #必须用else，如果再来个if，可能上面刚更新了下面就又更新了，不对，一次性只能更新一次\n",
    "        #         node = node.right\n",
    "        # return res\n",
    "            \n",
    "            \n",
    "\n",
    "    \n",
    "# 目标值: target = 3.5\n",
    "\n",
    "# 初始化:\n",
    "# node = 4\n",
    "# res = 4\n",
    "# 进入第一次循环:\n",
    "# 当前 node.val = 4\n",
    "# 计算差值 abs(target - node.val) = abs(3.5 - 4) = 0.5\n",
    "# 当前 res 的差值: abs(3.5 - 4) = 0.5\n",
    "# 由于 node.val 和 res 的差值相同，并且 node.val 不小于 res，所以不更新 res。\n",
    "# 因为 node.val 大于 target，我们要去 node 的左子节点。\n",
    "# 更新 node = node.left = 2\n",
    "\n",
    "# 进入第二次循环:\n",
    "# 当前 node.val = 2\n",
    "# 计算差值 abs(target - node.val) = abs(3.5 - 2) = 1.5\n",
    "# 当前 res 的差值仍然是 0.5。\n",
    "# 由于 node.val 的差值大于 res 的差值，所以不更新 res。\n",
    "# 因为 node.val 小于 target，我们要去 node 的右子节点。\n",
    "# 更新 node = node.right = 3\n",
    "\n",
    "# 进入第三次循环:\n",
    "# 当前 node.val = 3\n",
    "# 计算差值 abs(target - node.val) = 0.5\n",
    "# 当前 res 的差值还是 0.5。\n",
    "# 但由于 node.val 的差值与 res 的差值相同，并且 node.val 小于 res，所以更新 res = 3。\n",
    "# 因为 node.val 小于 target，但是 node 没有右子节点，所以更新 node = None。\n",
    "# 循环结束:\n",
    "# node 是 None，所以循环结束。\n",
    "# 返回的结果是 res = 3。\n",
    "\n",
    "\n",
    "        node = root\n",
    "        candidate = node.val\n",
    "\n",
    "        while node:\n",
    "\n",
    "            if node.val == target:\n",
    "                return node.val\n",
    "            \n",
    "            if abs(node.val-target) < abs(candidate-target) or (abs(node.val-target) == abs(candidate-target) and node.val<candidate):\n",
    "                candidate = node.val\n",
    "\n",
    "\n",
    "            if node.val < target:\n",
    "                node = node.right\n",
    "            else:\n",
    "                node = node.left\n",
    "\n",
    "        return candidate\n",
    "# 对于输入 root = [4,2,5,1,3] 和 target = 3.714286 的模拟：\n",
    "\n",
    "# 初始化:\n",
    "\n",
    "# node = 4\n",
    "# res = 4\n",
    "# 进入 while 循环:\n",
    "\n",
    "# node.val (4) 不等于 target，所以跳过第一个 if 语句。\n",
    "# 计算差值:\n",
    "# ∣\n",
    "# 4\n",
    "# −\n",
    "# 3.714286\n",
    "# ∣\n",
    "# =\n",
    "# 0.285714\n",
    "# ∣4−3.714286∣=0.285714\n",
    "# 当前 res = 4，其差值为 0.285714。\n",
    "# 因为两者的差值相同但 node.val 并不小于 res，所以不会更新 res。\n",
    "# 由于 node.val = 4 大于 target，所以移动到左子节点 2。\n",
    "# 继续 while 循环:\n",
    "\n",
    "# node.val (2) 不等于 target。\n",
    "# 计算差值:\n",
    "# ∣\n",
    "# 2\n",
    "# −\n",
    "# 3.714286\n",
    "# ∣\n",
    "# =\n",
    "# 1.714286\n",
    "# ∣2−3.714286∣=1.714286\n",
    "# res 与 target 的差值 (0.285714) 更小，所以不会更新 res。\n",
    "# 由于 node.val = 2 小于 target，所以移动到右子节点 3。\n",
    "# 继续 while 循环:\n",
    "\n",
    "# node.val (3) 不等于 target。\n",
    "# 计算差值:\n",
    "# ∣\n",
    "# 3\n",
    "# −\n",
    "# 3.714286\n",
    "# ∣\n",
    "# =\n",
    "# 0.714286\n",
    "# ∣3−3.714286∣=0.714286\n",
    "# res 与 target 的差值 (0.285714) 更小，所以不会更新 res。\n",
    "# 由于 node.val = 3 小于 target，所以移动到右子节点，但 3 节点的右子节点是 None。\n",
    "# node 为 None，结束 while 循环。\n",
    "\n",
    "# 返回 res，其值为 4，与预期的输出一致。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            if abs(node.val - target ) < abs(ans-target):\n",
    "                    ans=node.val\n",
    "            if abs(node.val - target ) == abs(ans-target):\n",
    "                if node.val <ans:\n",
    "                    ans=node.val\n",
    "            if node.val >target:\n",
    "                dfs(node.left)\n",
    "            elif node.val <target:\n",
    "                dfs(node.right)\n",
    "            return\n",
    "        \n",
    "        ans=root.val\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        def dfs(node):\n",
    "            x,y=abs(node.val-target),node.val\n",
    "            if node.left:\n",
    "                a,b=dfs(node.left)\n",
    "                if a<x:\n",
    "                    x,y=a,b\n",
    "                if a==x:\n",
    "                    y=min(y,b)\n",
    "            if node.right:\n",
    "                a,b=dfs(node.right)\n",
    "                if a<x:\n",
    "                    x,y=a,b\n",
    "                if a==x:\n",
    "                    y=min(y,b)\n",
    "            return (x,y)\n",
    "        return dfs(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        if root.val > target:\n",
    "            if root.left is None:\n",
    "                return root.val\n",
    "            left_closest_value = self.closestValue(root.left, target)\n",
    "            if abs(left_closest_value - target) > root.val - target:\n",
    "                return root.val\n",
    "            else:\n",
    "                return left_closest_value\n",
    "        else:\n",
    "            if root.right is None:\n",
    "                return root.val\n",
    "            right_closest_value = self.closestValue(root.right, target)\n",
    "            if abs(right_closest_value - target) >= target - root.val:\n",
    "                return root.val\n",
    "            else:\n",
    "                return right_closest_value\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        min_val = 2.1e9\n",
    "        t_node = None\n",
    "        stack = []\n",
    "        node = root\n",
    "        while len(stack) > 0 or node is not None:\n",
    "            if node is not None:\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = stack.pop()\n",
    "                if node.val < target:\n",
    "                    min_val = min(min_val, target-node.val)\n",
    "                    t_node = node.val\n",
    "                else:\n",
    "                    if node.val - target < min_val:\n",
    "                        return node.val\n",
    "                    else:\n",
    "                        return t_node\n",
    "                node = node.right\n",
    "        return t_node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        ans, mi = root.val, inf\n",
    "        while root:\n",
    "            t = abs(root.val - target)\n",
    "            if t < mi or (t == mi and root.val < ans):\n",
    "                mi = t\n",
    "                ans = root.val\n",
    "            if root.val > target:\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = root.right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        \n",
    "        def dfs_close(root: TreeNode ):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return \n",
    "            if abs(root.val - target )<abs(ans - target):\n",
    "            \n",
    "                ans = root.val\n",
    "            elif abs(root.val - target ) == abs(ans - target):\n",
    "                ans =min(root.val,ans) #要输出小的那一个\n",
    "            if root.val >target:\n",
    "                \n",
    "                dfs_close(root.left)\n",
    "            elif root.val < target:\n",
    "                dfs_close(root.right)\n",
    "            return \n",
    "        ans = inf# 正无穷可以直接写 inf 不用加 float\n",
    "        dfs_close(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        self.res = float('INF')\n",
    "\n",
    "        self.traverse(root, target)\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root, target):\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        if root.val > target:\n",
    "            self.traverse(root.left, target)\n",
    "\n",
    "            if abs(root.val - target) < abs(self.res - target):\n",
    "                self.res = root.val\n",
    "                \n",
    "        else:\n",
    "            if abs(root.val - target) < abs(self.res - target):\n",
    "                self.res = root.val \n",
    "\n",
    "            self.traverse(root.right, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        self.min_diff = float('inf')\n",
    "        self.res = None\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return  \n",
    "            if root.val >= target:\n",
    "                dfs(root.left) \n",
    "            if self.res is None or abs(root.val - target) < abs(self.res - target):\n",
    "                self.res = root.val\n",
    "            if root.val <= target:\n",
    "                dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "# If there are multiple answers, print the smallest. for [4,2,5,1,3], print 3 not 4\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        if root is None:\n",
    "            return float('inf')\n",
    "        if root.val == target:\n",
    "            return root.val\n",
    "        elif root.val < target:\n",
    "            r = self.closestValue(root.right, target)\n",
    "            return root.val if abs(root.val-target) <= abs(r - target) else r\n",
    "        else:\n",
    "            l = self.closestValue(root.left, target)\n",
    "            return l if abs(l - target) <= abs(root.val-target) else root.val\n",
    "\n",
    "\n",
    "        # best = l if abs(l-target) <= abs(r - target) else r\n",
    "        # if abs(root.val-target) < abs(best - target):\n",
    "        #     return root.val\n",
    "        # elif best == l and abs(root.val-target) == abs(best - target):\n",
    "        #     return l\n",
    "        # elif best == r and abs(root.val-target) == abs(best - target):\n",
    "        #     return root.val\n",
    "        # else:\n",
    "        #     return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        ret = root.val\n",
    "        mindiff = abs(root.val - target)\n",
    "        def dfs(node):\n",
    "            nonlocal ret, mindiff\n",
    "            if not node:\n",
    "                return\n",
    "            curr_diff = abs(node.val - target)\n",
    "            if curr_diff < mindiff:\n",
    "                mindiff = curr_diff\n",
    "                ret = node.val\n",
    "            elif curr_diff == mindiff and node.val < ret:\n",
    "                ret = node.val\n",
    "\n",
    "            if node.val < target:\n",
    "                dfs(node.right)\n",
    "            else:\n",
    "                dfs(node.left)\n",
    "        dfs(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        res = (root.val, abs(root.val - target))\n",
    "        if root.val > target:\n",
    "            tmpnode = root.left\n",
    "        else:\n",
    "            tmpnode = root.right\n",
    "        \n",
    "        while tmpnode:\n",
    "            if abs(tmpnode.val - target) < res[1]:\n",
    "                res = (tmpnode.val, abs(tmpnode.val - target))\n",
    "            elif abs(tmpnode.val - target) == res[1] and tmpnode.val < res[0]:\n",
    "                res = (tmpnode.val, abs(tmpnode.val - target))\n",
    " \n",
    "            if tmpnode.val > target:\n",
    "                tmpnode = tmpnode.left\n",
    "            else:\n",
    "                tmpnode = tmpnode.right \n",
    "            \n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        if not root:\n",
    "            return\n",
    "        differ = abs(root.val - target)\n",
    "        closest = root.val\n",
    "\n",
    "        def get_closest(root, differ, closest):\n",
    "            if not root:\n",
    "                return differ, closest\n",
    "            if root.left:\n",
    "                tmp = abs(root.left.val - target)\n",
    "                if tmp < differ:\n",
    "                    differ = tmp\n",
    "                    closest = root.left.val\n",
    "                if tmp == differ:\n",
    "                    closest = min(root.left.val, closest)\n",
    "            if root.right:\n",
    "                tmp = abs(root.right.val - target)\n",
    "                if tmp < differ:\n",
    "                    differ = tmp\n",
    "                    closest = root.right.val\n",
    "                if tmp == differ:\n",
    "                    closest = min(root.right.val, closest)\n",
    "            differ, closest = get_closest(root.left, differ, closest)\n",
    "            differ, closest = get_closest(root.right, differ, closest)\n",
    "            return differ, closest\n",
    "\n",
    "        _, closest = get_closest(root, differ, closest)\n",
    "        return closest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        # node = root\n",
    "        # candidate = node.val\n",
    "        # while node:\n",
    "        #     candidate = max((candidate, node.val), key=lambda x: -abs(x - target))\n",
    "        #     if node.val < target:\n",
    "        #         node = node.right\n",
    "        #     elif node.val > target:\n",
    "        #         node = node.left\n",
    "        #     else:\n",
    "        #         return node.val\n",
    "        # return candidate\n",
    "     \n",
    "        # node = root\n",
    "        # res = root.val\n",
    "        # has_change = True\n",
    "        # while has_change:\n",
    "        #     has_change = False\n",
    "        #     res = min(res, node.val,key=lambda x:(abs(x - target), x))\n",
    "        #     if node.left is not None and target < node.val:\n",
    "        #         node = node.left\n",
    "        #         has_change = True\n",
    "        #     elif node.right is not None and target > node.val:\n",
    "        #         node = node.right\n",
    "        #         has_change = True\n",
    "        # return res\n",
    "        node = root\n",
    "        res = root.val\n",
    "\n",
    "        while node:\n",
    "            # 如果当前节点更接近目标，或者距离相同但值较小，更新结果\n",
    "            if abs(target - node.val) < abs(target - res) or (abs(target - node.val) == abs(target - res) and node.val < res):\n",
    "                res = node.val\n",
    "\n",
    "            # 根据当前节点的值移动到左子树或右子树\n",
    "            if node.val < target:\n",
    "                node = node.right\n",
    "            else:\n",
    "                node = node.left\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        if not root:\n",
    "            return\n",
    "        differ = abs(root.val - target)\n",
    "        closest = root.val\n",
    "\n",
    "        def get_closest(root, differ, closest):\n",
    "            if not root:\n",
    "                return differ, closest\n",
    "            if root.left:\n",
    "                tmp = abs(root.left.val - target)\n",
    "                if tmp < differ:\n",
    "                    differ = tmp\n",
    "                    closest = root.left.val\n",
    "                if tmp == differ:\n",
    "                    closest = min(root.left.val, closest)\n",
    "            if root.right:\n",
    "                tmp = abs(root.right.val - target)\n",
    "                if tmp < differ:\n",
    "                    differ = tmp\n",
    "                    closest = root.right.val\n",
    "                if tmp == differ:\n",
    "                    closest = min(root.right.val, closest)\n",
    "            differ, closest = get_closest(root.left, differ, closest)\n",
    "            differ, closest = get_closest(root.right, differ, closest)\n",
    "            return differ, closest\n",
    "\n",
    "        _, closest = get_closest(root, differ, closest)\n",
    "        return closest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        res = root.val\n",
    "        while root:\n",
    "            if (abs(res - target) == abs (target - root.val)):\n",
    "                res = min(res,root.val)\n",
    "            else:\n",
    "                res = min(res, root.val, key = lambda x : abs(x-target))\n",
    "            root = root.left if target < root.val else root.right\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        if root.val > target and root.left:\n",
    "            left_val = self.closestValue(root.left, target)\n",
    "            return left_val if abs(left_val-target)<=abs(root.val-target) else root.val\n",
    "        elif root.val < target and root.right:\n",
    "            right_val = self.closestValue(root.right,target)\n",
    "            return root.val if abs(root.val-target)<=abs(right_val-target) else right_val\n",
    "        else:\n",
    "            return root.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        if not root:\n",
    "            return -1\n",
    "        res = root.val\n",
    "        smallestDiff = abs(root.val - target)\n",
    "        cur = root\n",
    "\n",
    "        while cur:\n",
    "            diff = abs(cur.val - target)\n",
    "            if diff < smallestDiff or diff == smallestDiff and cur.val < res:\n",
    "                smallestDiff = diff\n",
    "                res = cur.val\n",
    "\n",
    "            if cur.val == target:\n",
    "                return cur.val\n",
    "            elif cur.val < target:\n",
    "                cur = cur.right\n",
    "            else:\n",
    "                cur = cur.left\n",
    "\n",
    "        return res             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        temp = root\n",
    "        count = temp.val\n",
    "        while temp:\n",
    "            if temp.val == target:\n",
    "                return temp.val\n",
    "            elif temp.val < target:\n",
    "                if target-temp.val < abs(count-target):\n",
    "                    count = temp.val\n",
    "                elif target-temp.val == abs(count-target):\n",
    "                    count = temp.val\n",
    "                temp = temp.right\n",
    "\n",
    "\n",
    "            elif temp.val > target:\n",
    "                if temp.val-target<abs(count-target):\n",
    "                    count = temp.val\n",
    "                temp = temp.left\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        # https://www.youtube.com/watch?v=wued6gzSjI4&ab_channel=RenZhang\n",
    "        #注意改了test case所以有些区别，比如target =3.5， 应该返回3 而不是4\n",
    "        #如果两者距离目标的差的绝对值相同，我们会选择较小的那个值。）\n",
    "# 面试时解释思路：\n",
    "\n",
    "# 问题的核心:\n",
    "# 首先，我们要找到BST中最接近给定目标值的节点。BST的一个关键属性是，对于任何节点，其左子树的所有节点的值都小于该节点，\n",
    "# 而右子树的所有节点的值都大于该节点。\n",
    "\n",
    "# 简单直观的方法:\n",
    "# 一个直接的方法是遍历整个树，记录最接近目标值的节点。但是，由于BST的特性，我们实际上不需要遍历所有节点。\n",
    "\n",
    "# 优化的方法:\n",
    "\n",
    "# 我们从根节点开始，初始化 res 为根节点的值。\n",
    "# 在每一步，我们比较当前节点的值与目标值：\n",
    "# 如果它们相等，那么我们已经找到了最接近的值，可以直接返回。\n",
    "# 如果当前节点的值小于目标值，那么我们知道应该继续在右子树中查找，因为右子树中的所有值都比当前节点大。\n",
    "# 如果当前节点的值大于目标值，我们则在左子树中查找。\n",
    "# 更新最接近的值:\n",
    "# 在每一步，我们都会检查当前节点的值是否比我们到目前为止找到的最接近的值更接近目标值。如果是，我们更新 res。\n",
    "\n",
    "# 结束条件:\n",
    "# 我们继续这个过程，直到我们到达叶子节点或找到与目标值完全匹配的节点。\n",
    "\n",
    "# 返回结果:\n",
    "# 最后，我们返回 res，它存储了最接近目标值的节点的值。\n",
    "        \n",
    "\n",
    "#         node = root\n",
    "#         res = root.val\n",
    "\n",
    "#         while node: #still  a valid node \n",
    "# #             我们使用两个条件来检查是否应该更新 res:\n",
    "# # 当前节点的值是否比 res 更接近目标。\n",
    "# # 如果两者距离目标的差的绝对值相同，我们会选择较小的那个值。\n",
    "#             # 如果当前节点更接近目标，或者距离相同但值较小，更新结果\n",
    "#             if abs(target - node.val) < abs(target - res) or \\\n",
    "#              (abs(target - node.val) == abs(target - res) and node.val < res):\n",
    "#                 res = node.val\n",
    "\n",
    "#             # 根据当前节点的值移动到左子树或右子树\n",
    "#             if node.val < target:\n",
    "#                 node = node.right\n",
    "#             else:\n",
    "#                 node = node.left\n",
    "\n",
    "#         return res\n",
    "\n",
    "        node = root\n",
    "\n",
    "        res = node.val\n",
    "        while node:\n",
    "            if node.val == target:\n",
    "                return node.val\n",
    "            if abs(node.val -target)  < abs(res-target) or \\\n",
    "             (abs(node.val -target)  == abs(res-target) and node.val < res) :\n",
    "                res = node.val\n",
    "            \n",
    "            if node.val > target:\n",
    "                node = node.left #到最下面node，node.left=None， 然后下一轮while就停了\n",
    "            else: #必须用else，如果再来个if，可能上面刚更新了下面就又更新了，不对，一次性只能更新一次\n",
    "                node = node.right\n",
    "        return res\n",
    "            \n",
    "            \n",
    "\n",
    "    \n",
    "# 目标值: target = 3.5\n",
    "\n",
    "# 初始化:\n",
    "# node = 4\n",
    "# res = 4\n",
    "# 进入第一次循环:\n",
    "# 当前 node.val = 4\n",
    "# 计算差值 abs(target - node.val) = abs(3.5 - 4) = 0.5\n",
    "# 当前 res 的差值: abs(3.5 - 4) = 0.5\n",
    "# 由于 node.val 和 res 的差值相同，并且 node.val 不小于 res，所以不更新 res。\n",
    "# 因为 node.val 大于 target，我们要去 node 的左子节点。\n",
    "# 更新 node = node.left = 2\n",
    "# 进入第二次循环:\n",
    "# 当前 node.val = 2\n",
    "# 计算差值 abs(target - node.val) = abs(3.5 - 2) = 1.5\n",
    "# 当前 res 的差值仍然是 0.5。\n",
    "# 由于 node.val 的差值大于 res 的差值，所以不更新 res。\n",
    "# 因为 node.val 小于 target，我们要去 node 的右子节点。\n",
    "# 更新 node = node.right = 3\n",
    "# 进入第三次循环:\n",
    "# 当前 node.val = 3\n",
    "# 计算差值 abs(target - node.val) = 0.5\n",
    "# 当前 res 的差值还是 0.5。\n",
    "# 但由于 node.val 的差值与 res 的差值相同，并且 node.val 小于 res，所以更新 res = 3。\n",
    "# 因为 node.val 小于 target，但是 node 没有右子节点，所以更新 node = None。\n",
    "# 循环结束:\n",
    "# node 是 None，所以循环结束。\n",
    "# 返回的结果是 res = 3。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        class Answer:\n",
    "            # 由于可能有多个最接近目标值的数值，用数组记录\n",
    "            val = [root.val,]\n",
    "            min_D_value = abs(target - root.val)\n",
    "        node = root  # 初始化当前节点\n",
    "        while node:\n",
    "            # 每到达一个节点，都计算节点值和target的差值，全局维护这个值，只j记录最小的D_value并用数组储存其对应的值\n",
    "            # 当循环结束即到达叶子节点时，最小的D_value对应的节点数值就是最接近目标值target的数值\n",
    "            D_value = abs(node.val - target)\n",
    "            if D_value < Answer.min_D_value:\n",
    "                Answer.min_D_value = D_value  # 更新最小差值及其对应的结点值到新的空数组中\n",
    "                Answer.val.clear()\n",
    "                Answer.val.append(node.val)  \n",
    "            elif D_value == Answer.min_D_value:\n",
    "                Answer.val.append(node.val)\n",
    "\n",
    "            if target < node.val:  # 右子树的节点值只会更大，排除右子树\n",
    "                node = node.left\n",
    "            elif target > node.val:  # 同理\n",
    "                node = node.right\n",
    "            else:  # 节点值目标值相等，无需再进行搜索，直接跳出\n",
    "                Answer.val.clear()\n",
    "                Answer.val.append(node.val) \n",
    "                break\n",
    "        return min(Answer.val)\n",
    "        \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        ans, cur = root.val, root\n",
    "        while cur:\n",
    "            if cur.val == target:\n",
    "                ans = cur.val\n",
    "                break\n",
    "            if abs(cur.val-target) < abs(ans-target):\n",
    "                ans = cur.val\n",
    "            elif abs(cur.val-target) == abs(ans-target):\n",
    "                ans = min(cur.val, ans)\n",
    "            if cur.val < target:\n",
    "                cur = cur.right\n",
    "            else:\n",
    "                cur = cur.left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        # find parent or target \n",
    "        # find exactly smaller or bigger \n",
    "\n",
    "        l,r = root.val,root.val\n",
    "        while root:\n",
    "            if root.val > target:\n",
    "                r = root.val\n",
    "                root = root.left\n",
    "            else:\n",
    "                l = root.val\n",
    "                root = root.right\n",
    "        return l if abs(target - l) <= abs(target - r) else r \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        \"\"\" in-order traversal \"\"\"\n",
    "        def in_order_traversal(root):\n",
    "            if not root:\n",
    "                return\n",
    "            in_order_traversal(root.left)\n",
    "\n",
    "            nonlocal min_diff, closest_val\n",
    "            diff = abs(root.val - target)\n",
    "            if diff < min_diff:\n",
    "                min_diff = diff\n",
    "                closest_val = root.val\n",
    "            \n",
    "            in_order_traversal(root.right)\n",
    "\n",
    "        min_diff = math.inf\n",
    "        closest_val = None\n",
    "        in_order_traversal(root)\n",
    "        return closest_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "\n",
    "        if root.val > target and root.left is not None:\n",
    "            value = self.closestValue(root.left, target)\n",
    "            return value if abs(value - target) <= abs(root.val - target) else root.val\n",
    "\n",
    "        elif root.val < target and root.right is not None:\n",
    "            value = self.closestValue(root.right, target)\n",
    "            return value if abs(value - target) < abs(root.val - target) else root.val\n",
    "\n",
    "        else:\n",
    "            return root.val\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self._diff = float(\"inf\")\n",
    "        self._result = float(\"inf\")\n",
    "\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        self._dfs_1(root, target)\n",
    "        return self._result\n",
    "\n",
    "    def _dfs_1(self, root, target):\n",
    "        if not root:\n",
    "            return\n",
    "\n",
    "        val = root.val\n",
    "        diff = abs(val - target)\n",
    "\n",
    "        if self._diff > diff:\n",
    "            self._diff = diff\n",
    "            self._result = val\n",
    "\n",
    "        if self._diff == diff:\n",
    "            self._result = min(self._result, val)\n",
    "\n",
    "        if val < target:\n",
    "            self._dfs_1(root.right, target)\n",
    "\n",
    "        if val > target:\n",
    "            self._dfs_1(root.left, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        if not root:\n",
    "            return\n",
    "        differ = abs(root.val - target)\n",
    "        closest = root.val\n",
    "\n",
    "        def get_closest(root, differ, closest):\n",
    "            if not root:\n",
    "                return differ, closest\n",
    "            if root.left:\n",
    "                tmp = abs(root.left.val - target)\n",
    "                if tmp < differ:\n",
    "                    differ = tmp\n",
    "                    closest = root.left.val\n",
    "                if tmp == differ:\n",
    "                    closest = min(root.left.val, closest)\n",
    "            if root.right:\n",
    "                tmp = abs(root.right.val - target)\n",
    "                if tmp < differ:\n",
    "                    differ = tmp\n",
    "                    closest = root.right.val\n",
    "                if tmp == differ:\n",
    "                    closest = min(root.right.val, closest)\n",
    "            differ, closest = get_closest(root.left, differ, closest)\n",
    "            differ, closest = get_closest(root.right, differ, closest)\n",
    "            return differ, closest\n",
    "\n",
    "        _, closest = get_closest(root, differ, closest)\n",
    "        return closest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "\n",
    "        stack = list()\n",
    "        while root:\n",
    "            stack.append(root)\n",
    "            root = root.left\n",
    "\n",
    "        if target <= stack[-1].val:\n",
    "            return stack[-1].val\n",
    "\n",
    "        pre_root = None\n",
    "\n",
    "\n",
    "        while stack:\n",
    "            root = stack.pop()\n",
    "            if pre_root and pre_root.val <= target <=root.val:\n",
    "                if abs(target - pre_root.val) <= abs(target - root.val):\n",
    "                    return pre_root.val\n",
    "                else:\n",
    "                    return root.val \n",
    "            pre_root = root\n",
    "            node = root.right\n",
    "            while node:\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            if not stack:\n",
    "                max_val = root.val\n",
    "            \n",
    "\n",
    "        return max_val\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        ans=root.val\n",
    "        ab=abs(ans-target)\n",
    "        que=[root]\n",
    "        while(que):\n",
    "            p=que.pop(0)\n",
    "            if abs(p.val-target)<ab:\n",
    "                ans=p.val\n",
    "                ab=abs(p.val-target)\n",
    "            elif abs(p.val-target)==ab:\n",
    "                if p.val<ans:\n",
    "                    ans=p.val\n",
    "            if p.left:\n",
    "                que.append(p.left)\n",
    "            if p.right:\n",
    "                que.append(p.right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        node = root\n",
    "        res = root.val\n",
    "        has_change = True\n",
    "        #print (1 ) if node.left.left.left else print(0)\n",
    "        #print(  node.left.left.left)\n",
    "        #print( not node.left.left.left)#True\n",
    "        #print(  node.left.left.left is not None )# False\n",
    "        while has_change:\n",
    "            has_change = False\n",
    "            res = min(res, node.val, key= lambda x:(abs(x-target), x))\n",
    "            if   node.left  and target < node.val:\n",
    "                #print(node.val)\n",
    "                node = node.left\n",
    "                has_change = True\n",
    "            elif   node.right  and target >node.val:\n",
    "                node = node.right\n",
    "                has_change = True\n",
    "        return res\n",
    "        \n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# class Solution:\n",
    "#     def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "#         node = root\n",
    "#         res = root.val\n",
    "#         has_change = True\n",
    "#         while has_change:\n",
    "#             has_change = False\n",
    "#             res = min(res, node.val,key=lambda x:(abs(x - target), x))\n",
    "#             if node.left is not None and target < node.val:\n",
    "#                 node = node.left\n",
    "#                 has_change = True\n",
    "#             elif node.right is not None and target > node.val:\n",
    "#                 node = node.right\n",
    "#                 has_change = True\n",
    "#         return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        closest = 10000000000\n",
    "        diff = 10000000000\n",
    "        def helper(node):\n",
    "            nonlocal closest\n",
    "            nonlocal diff\n",
    "            if not node:\n",
    "                return\n",
    "            if abs(node.val - target) < diff:\n",
    "                closest = node.val\n",
    "                diff = abs(node.val - target)\n",
    "            elif abs(node.val - target) == diff:\n",
    "                if node.val < closest:\n",
    "                    closest = node.val\n",
    "            if node.val == target:\n",
    "                return\n",
    "            elif node.val > target:\n",
    "                helper(node.left)\n",
    "            else:\n",
    "                helper(node.right)\n",
    "        helper(root)\n",
    "        return closest\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "\n",
    "        if not root:\n",
    "            return\n",
    "\n",
    "        lower = self.get_lower(root, target)\n",
    "        upper = self.get_upper(root, target)\n",
    "        if not lower:\n",
    "            return upper.val\n",
    "        if not upper:\n",
    "            return lower.val\n",
    "\n",
    "        if target - lower.val <= upper.val - target:\n",
    "            return lower.val\n",
    "        return upper.val\n",
    "\n",
    "    def get_lower(self, root, target):\n",
    "        if not root:\n",
    "            return None\n",
    "        if target < root.val:\n",
    "            return self. get_lower(root.left, target)\n",
    "\n",
    "        lower = self.get_lower(root.right, target)\n",
    "        return root if not lower else lower\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def get_upper(self, root, target):\n",
    "        if not root:\n",
    "            return None\n",
    "        if target > root.val:\n",
    "            return self.get_upper(root.right, target)\n",
    "\n",
    "        upper = self.get_upper(root.left, target)\n",
    "        return root if not upper else upper\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        candidates = []\n",
    "        if target < root.val and root.left:\n",
    "            candidates.append(self.closestValue(root.left, target))\n",
    "        elif target > root.val and root.right:\n",
    "            candidates.append(self.closestValue(root.right, target))\n",
    "\n",
    "        ret = root.val\n",
    "        for c in candidates:\n",
    "            x, y = abs(c - target), abs(ret - target)\n",
    "            if x < y or (x == y and c < ret):\n",
    "                ret = c\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        if root.val == target:\n",
    "            return root.val\n",
    "        ans = root.val\n",
    "        while root:\n",
    "            if abs(root.val - target) < abs(ans - target):\n",
    "                ans = root.val\n",
    "            elif abs(root.val - target) == abs(ans - target):\n",
    "                ans = min(root.val, ans)\n",
    "            if root.val < target:\n",
    "                root = root.right\n",
    "            else:\n",
    "                root = root.left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        if root.val == target:\n",
    "            return target\n",
    "        ans = root.val\n",
    "        while root:\n",
    "            diff = abs(target - root.val) - abs(target - ans)\n",
    "            if diff < 0 or (diff == 0 and root.val < ans):\n",
    "                ans = root.val\n",
    "            elif root.val < target:\n",
    "                root = root.right\n",
    "            else:\n",
    "                root = root.left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "\n",
    "        if root.val > target and root.left is not None:\n",
    "            value = self.closestValue(root.left, target)\n",
    "            return value if abs(value - target) <= abs(root.val - target) else root.val\n",
    "\n",
    "        elif root.val < target and root.right is not None:\n",
    "            value = self.closestValue(root.right, target)\n",
    "            return value if abs(value - target) < abs(root.val - target) else root.val\n",
    "\n",
    "        else:\n",
    "            return root.val\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        if not root:\n",
    "            return\n",
    "        differ = abs(root.val - target)\n",
    "        closest = root.val\n",
    "\n",
    "        def get_closest(root, differ, closest):\n",
    "            if not root:\n",
    "                return differ, closest\n",
    "            if root.left:\n",
    "                tmp = abs(root.left.val - target)\n",
    "                if tmp < differ:\n",
    "                    differ = tmp\n",
    "                    closest = root.left.val\n",
    "                if tmp == differ:\n",
    "                    closest = min(root.left.val, closest)\n",
    "            if root.right:\n",
    "                tmp = abs(root.right.val - target)\n",
    "                if tmp < differ:\n",
    "                    differ = tmp\n",
    "                    closest = root.right.val\n",
    "                if tmp == differ:\n",
    "                    closest = min(root.right.val, closest)\n",
    "            differ, closest = get_closest(root.left, differ, closest)\n",
    "            differ, closest = get_closest(root.right, differ, closest)\n",
    "            return differ, closest\n",
    "\n",
    "        _, closest = get_closest(root, differ, closest)\n",
    "        return closest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        closest = math.inf\n",
    "        curr = root\n",
    "        while curr:\n",
    "            # handle current node\n",
    "            if abs(curr.val - target) == abs(closest - target):\n",
    "                closest = min(curr.val, closest)\n",
    "            else:\n",
    "                closest = min(closest, curr.val, key=lambda x: abs(x - target))\n",
    "            # consider the down tree direction\n",
    "            diff = curr.val - target\n",
    "            if diff == 0:\n",
    "                return closest\n",
    "            elif diff > 0:\n",
    "                curr = curr.left\n",
    "            elif diff < 0:\n",
    "                curr = curr.right\n",
    "        return closest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        candidates = []\n",
    "        if target < root.val and root.left:\n",
    "            candidates.append(self.closestValue(root.left, target))\n",
    "        elif target > root.val and root.right:\n",
    "            candidates.append(self.closestValue(root.right, target))\n",
    "\n",
    "        ret = root.val\n",
    "        for c in candidates:\n",
    "            x, y = abs(c - target), abs(ret - target)\n",
    "            if x < y or (x == y and c < ret):\n",
    "                ret = c\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        class Answer:\n",
    "            # 由于可能有多个最接近目标值的数值，用数组记录\n",
    "            val = [root.val,]\n",
    "            min_D_value = abs(target - root.val)\n",
    "        node = root  # 初始化当前节点\n",
    "        while node:\n",
    "            # 每到达一个节点，都计算节点值和target的差值，全局维护这个值，只j记录最小的D_value并用数组储存其对应的值\n",
    "            # 当循环结束即到达叶子节点时，最小的D_value对应的节点数值就是最接近目标值target的数值\n",
    "            D_value = abs(node.val - target)\n",
    "            if D_value < Answer.min_D_value:\n",
    "                Answer.min_D_value = D_value  # 更新最小差值及其对应的结点值到新的空数组中\n",
    "                Answer.val.clear()\n",
    "                Answer.val.append(node.val)  \n",
    "            elif D_value == Answer.min_D_value:\n",
    "                Answer.val.append(node.val)\n",
    "\n",
    "            if target < node.val:  # 右子树的节点值只会更大，排除右子树\n",
    "                node = node.left\n",
    "            elif target > node.val:  # 同理\n",
    "                node = node.right\n",
    "            else:  # 节点值目标值相等，无需再进行搜索，直接跳出\n",
    "                Answer.val.clear()\n",
    "                Answer.val.append(node.val) \n",
    "                break\n",
    "        return min(Answer.val)\n",
    "        \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "\n",
    "        l = r = root.val\n",
    "\n",
    "        while root:\n",
    "            if root.val > target:\n",
    "                r = root.val\n",
    "                root = root.left\n",
    "            elif root.val < target:\n",
    "                l = root.val\n",
    "                root = root.right\n",
    "            else:\n",
    "                return root.val\n",
    "        return l if abs(target - l) <= abs(r - target) else r\n",
    "        \n",
    "\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            \n",
    "            cur = root\n",
    "            stack = []\n",
    "            anw = []\n",
    "            close = int(1e9)\n",
    "            diff = int(1e9)\n",
    "\n",
    "            while stack or cur:\n",
    "                if cur:\n",
    "                    stack.append(cur)\n",
    "                    cur = cur.left\n",
    "                else:\n",
    "                    cur = stack.pop()\n",
    "                    cur_val = cur.val\n",
    "                    print(cur_val)\n",
    "                    if abs(cur_val - target) < diff:\n",
    "                        diff = abs(cur_val - target)\n",
    "                        print(diff)\n",
    "                        close = cur_val\n",
    "                    anw.append(cur.val)\n",
    "                    cur = cur.right\n",
    "        \n",
    "            return close\n",
    "        return inorder(root)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        self.res = inf\n",
    "        def dfs(root,target):\n",
    "            if not root: return\n",
    "            if abs(root.val - target) < abs(self.res - target):\n",
    "                self.res = root.val\n",
    "            if abs(root.val - target) == abs(self.res - target):\n",
    "                self.res = min(self.res,root.val)\n",
    "            dfs(root.left, target)\n",
    "            dfs(root.right,target)\n",
    "        \n",
    "        dfs(root,target)\n",
    "        return self.res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        candidates = []\n",
    "        if target < root.val and root.left:\n",
    "            candidates.append(self.closestValue(root.left, target))\n",
    "        if target > root.val and root.right:\n",
    "            candidates.append(self.closestValue(root.right, target))\n",
    "\n",
    "        ret = root.val\n",
    "        for c in candidates:\n",
    "            x, y = abs(c - target), abs(ret - target)\n",
    "            if x < y or (x == y and c < ret):\n",
    "                ret = c\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        global_min_diff = float(\"inf\")\n",
    "        min_val = None\n",
    "\n",
    "        def helper(root, target):\n",
    "            nonlocal global_min_diff\n",
    "            nonlocal min_val\n",
    "\n",
    "            if root:\n",
    "                diff = abs(root.val - target)\n",
    "                if diff < global_min_diff:\n",
    "                    global_min_diff = diff\n",
    "                    min_val = root.val\n",
    "                elif diff == global_min_diff and root.val < min_val:\n",
    "                    min_val = root.val\n",
    "                \n",
    "\n",
    "                helper(root.left, target)\n",
    "                helper(root.right, target)\n",
    "            \n",
    "        \n",
    "        helper(root, target)\n",
    "        return min_val\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        diff = float('inf')\n",
    "        cur = root\n",
    "        val = root.val\n",
    "        while cur is not None:\n",
    "            d = cur.val - target\n",
    "            if abs(d) < diff:\n",
    "                diff = abs(d)\n",
    "                val = cur.val\n",
    "            elif abs(d) == diff:\n",
    "                val = min(val, cur.val)\n",
    "            else:\n",
    "                pass\n",
    "                \n",
    "            if d < 0:\n",
    "                cur = cur.right\n",
    "            elif d > 0:\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                # d == 0\n",
    "                break\n",
    "        return val\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "\n",
    "        def dfs(node, target):\n",
    "            \n",
    "            if node.val > target and node.left:\n",
    "                left_v = dfs(node.left, target)\n",
    "                if abs(node.val - target) >= abs(left_v - target):\n",
    "                    return left_v\n",
    "                else:\n",
    "                    return node.val\n",
    "\n",
    "            elif node.val < target and node.right:\n",
    "                right_v = dfs(node.right, target)\n",
    "                if abs(node.val - target) > abs(right_v - target):\n",
    "                    return right_v\n",
    "                else:\n",
    "                    return node.val\n",
    "            \n",
    "            else:\n",
    "                return node.val\n",
    "        \n",
    "        return dfs(root, target)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        if root is None:\n",
    "            return float('inf')\n",
    "        if root.val == target:\n",
    "            return root.val\n",
    "        elif root.val < target:\n",
    "            r = self.closestValue(root.right, target)\n",
    "            return root.val if abs(root.val-target) <= abs(r - target) else r\n",
    "        else:\n",
    "            l = self.closestValue(root.left, target)\n",
    "            return l if abs(l - target) <= abs(root.val-target) else root.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        self.res = 0x7fffffff\n",
    "        self.minDiff = 0x7fffffff\n",
    "        def helper(node):\n",
    "            if not node:\n",
    "                return\n",
    "            diff = abs(node.val - target)\n",
    "            if diff < self.minDiff or (diff == self.minDiff and node.val < self.res):\n",
    "                # print(self.res, self.diff)\n",
    "                self.res = node.val\n",
    "                self.minDiff = diff\n",
    "            if node.val == target:\n",
    "                return node.val\n",
    "            elif node.val < target:\n",
    "                helper(node.right)\n",
    "            else:\n",
    "                helper(node.left)\n",
    "        helper(root)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        self.ans = inf\n",
    "        def dfs(root, target):\n",
    "            if not root:\n",
    "                return \n",
    "            if abs(root.val - target) < abs(self.ans - target):\n",
    "                self.ans = root.val\n",
    "            if abs(root.val - target) == abs(self.ans - target):\n",
    "                self.ans = min(self.ans, root.val)\n",
    "            dfs(root.left, target)\n",
    "            dfs(root.right, target)\n",
    "        \n",
    "        dfs(root, target)\n",
    "        \n",
    "        return self.ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        # 简单地按照搜索树的规则进行，到达叶子节点时，即可得到了\n",
    "        min_chazhi = abs(root.val - target)\n",
    "        result = root.val\n",
    "        cur_node = root\n",
    "        while cur_node:\n",
    "            chazhi = abs(cur_node.val - target)\n",
    "            if chazhi == min_chazhi:\n",
    "                result = min(result, cur_node.val)\n",
    "            elif chazhi < min_chazhi:\n",
    "                min_chazhi = chazhi\n",
    "                result = cur_node.val\n",
    "            if target > cur_node.val:\n",
    "                cur_node = cur_node.right\n",
    "            elif target < cur_node.val:\n",
    "                cur_node = cur_node.left\n",
    "            else:\n",
    "                return cur_node.val\n",
    "        return result\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        if root is None:\n",
    "            return float('inf')\n",
    "        l = self.closestValue(root.left, target)\n",
    "        r = self.closestValue(root.right, target)\n",
    "\n",
    "        best = l if abs(l-target) <= abs(r - target) else r\n",
    "        if abs(root.val-target) < abs(best - target):\n",
    "            return root.val\n",
    "        elif best == l and abs(root.val-target) == abs(best - target):\n",
    "            return l\n",
    "        elif best == r and abs(root.val-target) == abs(best - target):\n",
    "            return root.val\n",
    "        else:\n",
    "            return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        def closestdiff(root, target):\n",
    "            if root.val > target:\n",
    "                if root.left is None:\n",
    "                    return root.val - target\n",
    "                else:\n",
    "                    v = closestdiff(root.left, target)\n",
    "                    if root.val-target >= abs(v):\n",
    "                        return v\n",
    "                    else:\n",
    "                        return root.val-target\n",
    "            if root.val < target:\n",
    "                if root.right is None:\n",
    "                    return root.val - target\n",
    "                else:\n",
    "                    v = closestdiff(root.right, target)\n",
    "                    if target - root.val > abs(v):\n",
    "                        return v\n",
    "                    else:\n",
    "                        return root.val - target\n",
    "            return 0\n",
    "        return int(closestdiff(root, target) + target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        if root.left == None and root.right == None:\n",
    "            return root.val\n",
    "        if root.val == target:\n",
    "            return root.val\n",
    "        closest = -1\n",
    "        if root.val > target and root.left != None:\n",
    "            closest = self.closestValue(root.left, target)\n",
    "        elif root.right != None:\n",
    "            closest = self.closestValue(root.right, target)\n",
    "\n",
    "        closest_diff = abs(closest - target)\n",
    "        target_diff = abs(root.val - target)\n",
    "        if closest_diff == target_diff:\n",
    "            return min(closest, root.val)\n",
    "        elif closest_diff < target_diff:\n",
    "            return closest\n",
    "        else:\n",
    "            return root.val\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        diff = inf\n",
    "        res = inf\n",
    "        while root:\n",
    "            cur_diff = abs(root.val - target)\n",
    "            if cur_diff == diff:\n",
    "                res = min(res, root.val)\n",
    "            if cur_diff < diff:\n",
    "                diff = cur_diff\n",
    "                res = root.val\n",
    "                \n",
    "\n",
    "            if root.val == target:\n",
    "                return root.val\n",
    "            elif root.val > target:\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = root.right\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        data = []\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            data.append(root.val)\n",
    "            dfs(root.right)\n",
    "\n",
    "        dfs(root)\n",
    "        index = bisect.bisect_left(data, target)\n",
    "        res = 0\n",
    "        diff = float('inf')\n",
    "        for i in range(len(data)):\n",
    "            if diff > abs(data[i] - target):\n",
    "                diff = abs(data[i] - target)\n",
    "                res = data[i]\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self._diff = float(\"inf\")\n",
    "        self._result =float(\"inf\")\n",
    "\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        self._dfs(root, target)\n",
    "        return self._result\n",
    "\n",
    "    def _dfs(self, root, target):\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        diff  = abs(root.val - target)\n",
    "        if diff<self._diff:\n",
    "            self._result =  root.val\n",
    "            self._diff = diff\n",
    "        if diff == self._diff:\n",
    "            self._result = min(self._result, root.val)\n",
    "        \n",
    "\n",
    "        if root.val > target:\n",
    "            self._dfs(root.left, target)\n",
    "        elif root.val< target:\n",
    "            self._dfs(root.right, target)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        min_diff = float(\"inf\")\n",
    "        closest_val = None\n",
    "\n",
    "        while root:\n",
    "            diff = abs(root.val - target)\n",
    "            if diff < min_diff:\n",
    "                min_diff, closest_val = diff, root.val\n",
    "            \n",
    "            if diff == min_diff:\n",
    "                closest_val = min(closest_val, root.val)\n",
    "            \n",
    "            if root.val > target:\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = root. right\n",
    "        return closest_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "        global_min_diff = float(\"inf\")\n",
    "        min_val = None\n",
    "\n",
    "        def helper(root, target):\n",
    "            nonlocal global_min_diff\n",
    "            nonlocal min_val\n",
    "\n",
    "            if root:\n",
    "                diff = abs(root.val - target)\n",
    "                if diff < global_min_diff:\n",
    "                    global_min_diff = diff\n",
    "                    min_val = root.val\n",
    "                elif diff == global_min_diff and root.val < min_val:\n",
    "                    min_val = root.val\n",
    "                \n",
    "\n",
    "                helper(root.left, target)\n",
    "                helper(root.right, target)\n",
    "            \n",
    "        \n",
    "        helper(root, target)\n",
    "        return min_val\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestValue(self, root: Optional[TreeNode], target: float) -> int:\n",
    "\n",
    "        candidate = root.val\n",
    "\n",
    "        while root:\n",
    "\n",
    "            if abs(target- candidate) >abs(target-root.val) or  abs(target- candidate) ==abs(target-root.val) and root.val<candidate:\n",
    "                candidate = root.val\n",
    "\n",
    "            if root.val >target:\n",
    "                root = root.left\n",
    "            else: \n",
    "                root = root.right\n",
    "        return candidate"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
